#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};



class Solution {
public:
    ListNode* head;
public:
    void deleteNode(ListNode* node) {
        ListNode* head_pre = NULL;
        ListNode* head_bak = head;
        while(head){
            if (head->val == node->val){
                if (!head_pre){
                    ListNode* temp;
                    temp = head;
                    head = head->next;
                    delete temp;
                    break;
                }else{
                    head_pre->next = head->next;
                    delete head;
                    head = head_bak;
                    break;
                }
            }
            head_pre = head;
            head = head->next;
        }
    }
};

ListNode* createList(int num, uint32_t max)
{
    ListNode* head;
    ListNode* node;
    if (0 == num) return NULL;
    srand(clock());
    head = new ListNode(rand()%max);
    node = head;
    for (int i = 0; i < num-1; i++){
        node->next = new ListNode(rand()%max);
        node = node->next;
    }
    return head;
}

void printList(ListNode* node)
{
    int cnt = 0;
    while(node){
        cout << ++cnt << ":" << node->val << endl;
        node = node->next;
    }
}

ListNode* getRandomNode(ListNode* node)
{
    int cnt = 0;
    ListNode* selNodeBak = node;
    while(node){
        cnt++;
        node = node->next;
    }
    srand(clock());
    int sel = rand()%cnt;
    int i;
    ListNode* selNode = selNodeBak;
    for (i = 0; i < sel; i++){
        selNodeBak = selNode;
        selNode = selNode->next;
    }
    cout << "get random node is: ";
    cout << i << ":" << selNodeBak->val << endl;
    return selNodeBak;
}


int main(void)
{
    Solution su;
    su.head = createList(50, 100);
    printList(su.head);
    ListNode* node = getRandomNode(su.head);
    su.deleteNode(node);
    printList(su.head);
    return 0;
}
